package com.mlh.backtracking;

import java.util.*;

/**
 * @author 缪林辉
 * @date 2024/4/6 13:03
 * @DESCRIPTION
 */
// 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，
// 递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
// 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。(非严格递增)
// 输入：nums = [4,6,7,7]
// 输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
public class 非递减子序列 {
    LinkedList<Integer> path = new LinkedList<>();// 路径
    List<List<Integer>> res = new ArrayList<>();// 最终结果
    public List<List<Integer>> findSubsequences(int[] nums) {
        recursion(0, 0, nums);
        return res;
    }

    public void recursion(int head, int floor, int[] nums) {
        if (floor >= 2) {//用floor来控制递增子序列至少有两个元素
            res.add(new ArrayList<>(path));
        }
        if (head >= nums.length) {
            return;
        }
        //因为这里元素重复，没办法对nums数组进行排序处理，因此利用set来处理元素重复问题
        HashSet<Integer> dup = new HashSet<>();
        for (int i = head; i < nums.length; i++) {
            //在同一层树中，元素重复跳过
            //本层树中小于上一层的元素也跳过，因为无法形成递增子序列
            if (dup.contains(nums[i]) || path.size() > 0 && path.peekLast() > nums[i]) {
                continue;
            }
            dup.add(nums[i]);
            path.add(nums[i]);
            recursion(i + 1, floor + 1, nums);
            path.removeLast();
        }
    }
}
